public class QuickSort {
    public static void main(String[] args) {
        QuickSort q = new QuickSort();
        int[] arr = new int[]{9,1,9,9,9,9};
        quickSort(arr);
        for(int x: arr) {
            System.out.print(x + " ");
        }
    }

    private static void quickSort(int[] arr) {
        /**
         * 快速排序-接口层*/
        quick(arr, 0, arr.length-1);
    }

    private static void quick(int[] arr, int left, int right) {
        /**
         * 快速排序-递归层*/
        if(left >= right) {
            return;
        }
        // 1 找到划分点
        int pivot = partition(arr, left, right);
        // 2 对左右区间进行递归操作
        quick(arr, left, pivot - 1);
        quick(arr, pivot + 1, right);
    }

    private static int partition(int[] arr, int left, int right) {
        /**
         * 划分函数*/
        // 1 记录基准点 及其 基准点下标
        int target = arr[left];
        int initialIndex = left;

        // 2 按照基准点对数组进行划分，基准点左边小于等于基准值，基准点右边大于基准值
        while(left < right) {
            while(left < right && arr[right] >= target) {
                right --;
            }
            while(left < right && arr[left] <= target) {
                left ++;
            }
            // -出循环交换
            swap(arr, left, right);
        }

        // 3 出循环，划分完成，交换基准值，并返回基准点
        swap(arr, left, initialIndex);
        return left;
    }

    private static void swap(int[] arr, int a, int b) {
        /**
         * 交换函数*/
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
